
//3112.访问消失节点的最少时间
class Solution {
public:
    vector<int> minimumTime(int n, vector<vector<int>>& edges, vector<int>& disappear) {
        //使用Dijkstra算法
        
        //使用堆来实现
        //1. 先统计每个两个位置之间的时间关系
        vector<vector<pair<int,int>>> path(n);
        for(auto& tmp:edges)
        {
            int x = tmp[0],y = tmp[1] ,t = tmp[2];
            path[x].emplace_back(y,t);
            path[y].emplace_back(x,t);
        }

        //2. 循环前的准备工作:设置最短时间数组+已经作为扩展起点的位置
        vector<int> dis(n,INT_MAX/2);
        vector<int> vist(n);
        priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;    //记录时间以及位置
        vist[0] = 1;
        pq.push({0,0});  
        while(pq.size())
        {
            int clock = pq.top().first,x = pq.top().second;
            pq.pop();
            if(dis[x] <= clock)  continue;
            dis[x] = clock;
            vist[x] = 1;
            for(auto& [next,t]: path[x])
            {   
                if(t + clock <dis[next] && disappear[next] > t + clock && !vist[next]) 
                    pq.push({t + clock,next});
            }
        }        
        for(auto& x:dis)
            if(x==INT_MAX/2) x = -1;

        return dis;
    }
};